1.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为       

A) 4         B) 5         C) 6         D) 7

【答案】B。注意对栈为先进后出，可能序列为abc、bac、cba、acb、bca，共计5种。

2.最不适合用作链式队列的链表是( )。 A.只带队首指针的非循环双链表 B.只带队首指针的循环双链表 C.只带队尾指针的循环双链表 D.只带队尾指针的循环单链表

【答案】A。由于非循环双链表只带队首指针，在执行入队操作时需要修改队尾结点的指针域，而查找队尾结点需要0(n)的时间。B、C和D均可在0(1)的时间内找到队首和队尾。

3. 栈S最多能容纳4个元素。现在6个元素按A、B、C、D、E、F的顺序进栈，下列哪一个序列是不可能的出栈序列？

A) A、B、C、D、E、F            B) A、F、E、D 、C、B

C) C、B、E、D、A、F            D) C、D、B、F、 E、 A

【答案】B。选项A，A进栈后出栈、B进栈后出栈、C进栈后出栈、D进栈后出栈、E进栈后出栈、F进栈后出栈，栈只使用了一个容量并可得到A选项所对应的结果。

选项B，A进栈后出栈、B进栈、C进栈、D进栈、E进栈此时栈S满，F无法进栈，因此不可能出现该序列

选项C，A进栈、B进栈、C进栈后出栈、B出栈、D进栈、E进栈后出栈、D出栈、A出栈、F进栈后出栈，得到C选项所对应的结果，并且栈所占最大容量为3符合题目要求。

选项D，A进栈、B进栈、C进栈后出栈、D进栈后出栈、B出栈、E进栈、F进栈后出栈、E出栈、A出栈，得到D选项所对应的结果且栈所占最大容量为3符合题目要求。

4. 循环队列存储在数组A[0..m]中，则入队时的操作为（    ）。

   A. rear=rear+1                   B. rear=(rear+1) mod (m-1)

  C. rear=(rear+1) mod m       D. rear=(rear+1) mod (m+1)

【答案】D。注意数组A[0..m]共存储(m+1)个元素。

5. 若已知一个栈的入栈序列是1, 2, 3, …, n，其输出序列为p1, p2，p3，…，pn，

若p1=n，则pi为 (      )

   A．i       B．n=i      C．n-i+1       D．不确定

【答案】C。此题可使用特殊值法进行计算，如入栈序列为1, 2, 3, 4, 5, 6,7,8，其输出序列为p1, p2，p3，…，pn，则p1=8，p2=7，p3=6，p4=5，p5=4….按照此规律可得下标i与n的关系。

6. 设有一个递归算法如下：

int fact(int n) { //n大于等于 0

   if(n